{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numOfSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #大小为 K 且平均值大于等于阈值的子数组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code>&nbsp;和两个整数 <code>k</code>&nbsp;和 <code>threshold</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回长度为 <code>k</code>&nbsp;且平均值大于等于&nbsp;<code>threshold</code>&nbsp;的子数组数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= arr.length</code></li>\n",
    "\t<li><code>0 &lt;= threshold &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold](https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold](https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,2,2,5,5,5,8]\\n3\\n4', '[11,13,17,23,29,31,7,5,2,3]\\n3\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        cur, res = 0, 0\n",
    "        for i in range(k - 1):\n",
    "            cur += arr[i]\n",
    "        for i in range(k - 1, len(arr)):\n",
    "            cur += arr[i]\n",
    "            if cur // k >= threshold:\n",
    "                res += 1\n",
    "            cur -= arr[i - k + 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        res = 0\n",
    "        if len(arr) < k:\n",
    "            return 0\n",
    "        target = threshold * k\n",
    "        curr = sum(arr[0:k])\n",
    "        if curr >= target:\n",
    "            res += 1\n",
    "        for i in range(k, len(arr)):\n",
    "            curr = curr - arr[i - k] + arr[i]\n",
    "            if curr >= target:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        start = 0\n",
    "        end = k-1\n",
    "        threshold *= k\n",
    "        sum = 0\n",
    "        answer = 0\n",
    "        for i in range(start,end):\n",
    "            sum += arr[i]\n",
    "        while end < len(arr):\n",
    "            sum+=arr[end]\n",
    "            if sum>=threshold:\n",
    "                answer+=1\n",
    "            sum-=arr[start]\n",
    "            start+=1\n",
    "            end+=1\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        presum=[0]\n",
    "        for a in arr:\n",
    "            presum.append(presum[-1]+a-threshold)\n",
    "        res=0\n",
    "        for i in range(len(presum)-k):\n",
    "            if presum[i+k]-presum[i]>=0:\n",
    "                res+=1 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        res = 0\n",
    "        threshold *= k\n",
    "        ls = []\n",
    "        for i in range(k):\n",
    "            ls.append(arr.pop())\n",
    "        average = sum(ls)\n",
    "        if average >= threshold:\n",
    "            res += 1\n",
    "        while arr:\n",
    "            average -= ls.pop(0)\n",
    "            ls.append(arr.pop())\n",
    "            average += ls[-1]\n",
    "            if average >= threshold:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        num = 0\n",
    "        if len(arr) < k:\n",
    "            return 0\n",
    "        else:\n",
    "            total = sum(arr[:k])\n",
    "            if total >= k * threshold:\n",
    "                num += 1\n",
    "            for i in range(len(arr) - k):\n",
    "                total = total + (arr[i + k] - arr[i])\n",
    "                if total >= k * threshold:\n",
    "                    num += 1\n",
    "                    print('yes')\n",
    "            return num\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        target=k*threshold\n",
    "        cur=sum(arr[:k])\n",
    "        ans=0\n",
    "        n=len(arr)\n",
    "        for i in range(k,n):\n",
    "            if cur>=target:\n",
    "                ans+=1\n",
    "            cur+=arr[i]\n",
    "            cur-=arr[i-k]\n",
    "        if cur>=target:\n",
    "            ans+=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        result = 0\n",
    "        arr.insert(0, 0)\n",
    "        pre_sums = list(accumulate(arr))\n",
    "        i, j = 0, k\n",
    "        while j < len(pre_sums):\n",
    "            tmp_sum = (pre_sums[j] - pre_sums[i])\n",
    "            if tmp_sum // k >= threshold:\n",
    "                result += 1\n",
    "            j += 1\n",
    "            i += 1\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        j=k*threshold\n",
    "        value = 0\n",
    "        count = 0\n",
    "        for i in range(len(arr)):\n",
    "            if i <k:\n",
    "                value += arr[i]\n",
    "                if i == k-1 and value >= j:\n",
    "                    count += 1\n",
    "            else:\n",
    "                value = value + arr[i] - arr[i-k]\n",
    "                if value >=j:\n",
    "                    count += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        init_val = sum(arr[:k])\n",
    "        res = 0\n",
    "        len_arr = len(arr)\n",
    "        if init_val / k >= threshold:\n",
    "            res += 1\n",
    "        for i in range(k, len_arr):\n",
    "            init_val = init_val + arr[i] - arr[i - k]\n",
    "            if init_val / k >= threshold:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        ans = 0\n",
    "        temp = sum(arr[:k])\n",
    "        target = k * threshold\n",
    "        if temp >= target:\n",
    "            ans = 1\n",
    "        for i in range(k,len(arr)):\n",
    "            temp = temp - arr[i-k] + arr[i]\n",
    "            if temp >= target:\n",
    "                ans += 1\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        left, right = 0, 0\n",
    "        window_sum, ans = 0, 0\n",
    "        while right < len(arr):\n",
    "            window_sum += arr[right]\n",
    "            if right - left + 1 >= k:\n",
    "                if window_sum >= k * threshold:\n",
    "                    ans += 1\n",
    "                window_sum -= arr[left]\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        valid_num = 0\n",
    "        window_sum = 0\n",
    "        for i in range(k):\n",
    "            window_sum += arr[i]\n",
    "        if window_sum/k >= threshold:\n",
    "            valid_num += 1\n",
    "        for i in range(1,len(arr)-k+1):\n",
    "            window_sum += arr[i+k-1] - arr[i-1]\n",
    "            if window_sum/k >= threshold:\n",
    "                valid_num += 1\n",
    "        return valid_num\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "        ans = 0\n",
    "        pre_sum = 0\n",
    "        target = k * threshold        \n",
    "        for i in range(len(arr)) :\n",
    "            pre_sum += arr[i]\n",
    "            if i > k - 1:\n",
    "                pre_sum -= arr[i - k]\n",
    "            if i >= k - 1 and pre_sum >= target:\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:\n",
    "    t = threshold * k\n",
    "    s = sum(arr[:k])\n",
    "    ret = 0\n",
    "    if s >= t:\n",
    "      ret += 1\n",
    "    for i in range(k, len(arr)):\n",
    "      s -= arr[i - k]\n",
    "      s += arr[i]\n",
    "      if s >= t:\n",
    "        ret += 1\n",
    "    return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
